python3

2023-10-04 23:05| 来源: 网络整理| 查看: 265

参考：https://labuladong.github.io/algo/1/4/

感谢大神

本文除了将参考中提到的题目改写为python3外，还增加了自己刷的题目及体会。共同加油。

【简单】21. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/ 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

思路：使用虚的头节点dummy，p1和p2用来遍历list1和list2，p是结果链表的尾巴。

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() p = dummy p1 = list1 p2 = list2 while p1 != None and p2 != None: if p1.val Optional[ListNode]: dummy1 = ListNode() # 虚的头节点 dummy2 = ListNode() p1 = dummy1 # 存放值小于x的节点 p2 = dummy2 # 存放其它节点 p = head # p用来遍历原链表 while p != None: if p.val Optional[ListNode]: dummy = ListNode() dummy.next = head p = dummy while p != None: p1 = p.next if p1 != None and p1.val == val: p.next = p1.next else: p = p.next return dummy.next 【简单】206. 反转链表

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

思路：reverseList(head)定义为反转以head为头的列表并且返回新的链表头

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # 终止条件 if head == None or head.next == None: return head last = self.reverseList(head.next) # 此时head.next指的是last为头链表的最后一个元素，所以把这个元素的next改为head， # 就完成了链表的反转 head.next.next = head # 修改. 这个必须要有，不然会无法终止 head.next = None return last 【中等】92. 反转链表 II

在这里插入图片描述

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next successor = ListNode() class Solution: # 反转前n个节点，返回新的头节点 def reverseN(self, head:Optional[ListNode], n:int)->Optional[ListNode]: global successor if n == 1: successor = head.next return head last = self.reverseN(head.next, n-1) head.next.next = head head.next = successor return last def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: if left == 1: return self.reverseN(head, right) head.next = self.reverseBetween(head.next, left - 1, right - 1) return head 2. 两数相加

https://leetcode.cn/problems/add-two-numbers

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。思路：使用一个指针前进，一个指针作为头。

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: ans = ListNode(-1) p = ans p1 = l1 p2 = l2 c = 0 while p1 != None or p2 != None or c > 0: val = c if p1 != None: val += p1.val p1 = p1.next if p2 != None: val += p2.val p2 = p2.next p.next = ListNode(val % 10) c = val // 10 p = p.next p.next = None return ans.next

【本文地址】

python3

python3

今日新闻

推荐新闻